Königsberg sat on the river Pregel. The river split around an island and divided the city into four pieces of land joined by seven bridges. The puzzle was simple to state: can you walk through the city and cross every bridge exactly once? People tried, and nobody managed it. But nobody could prove it was impossible either.
Euler's paper on it was presented to the St Petersburg Academy in 1735 and published in a volume dated 1736. He noticed that almost nothing about the city matters. Not the street layout, not the length of the bridges, not the shape of the island. All that matters is which pieces of land are joined to which, and how many times. Shrink each piece of land to a dot and each bridge to a line, and you have what we now call a graph: dots (vertices) joined by lines (edges).
Think about any dot you pass through on your walk. Every time you arrive by one bridge, you must leave by another. So the bridges at that dot get used up in pairs, and the dot needs an even number of them. The only dots allowed an odd number are the one where you start and the one where you finish.
So a walk that uses every line exactly once is possible only if zero or two dots have an odd number of lines (and the whole graph is connected). With zero you can even end where you started. In Königsberg the island had 5 bridges and each of the other three pieces of land had 3. Four odd dots. Impossible, and no amount of trying would ever change that.
Tap a bridge to demolish it or build it back. The two dashed bridges are new ones you can add. Each piece of land shows how many bridges touch it.
Try demolishing any one bridge. Suddenly only two dots are odd, and a route appears. Now try to make exactly one dot odd. You can't. Every line has two ends, so the total count of line-ends is always even, which forces the number of odd dots to be even too. That small fact is sometimes called the handshake lemma: at any party, the number of people who have shaken an odd number of hands is even.
Euler's breakthrough wasn't a calculation. It was deciding what to ignore.
Königsberg's own story ended badly. Two of the seven bridges did not survive the bombing of the city in the Second World War, and the city is now Kaliningrad, in Russia. The puzzle outlived the bridges.
Any time the important thing is what connects to what, you have a graph. Your friends form one. In a famous 1967 experiment the psychologist Stanley Milgram asked people in Omaha, Nebraska, to get a folder to a stranger in Boston by passing it through people they knew. The chains that arrived were short, with around five intermediaries, and that is where the phrase "six degrees of separation" comes from. (Critics point out that many folders never arrived and that the starters were not a random sample.)
Mathematicians have their own version. Paul Erdős wrote papers with so many co-authors that people count their Erdős number: 1 if you wrote a paper with him, 2 if you wrote one with one of his co-authors, and so on. The typical mathematician with a finite Erdős number has an Erdős number of 5. Web pages linking to each other, molecules, power grids and the neurons in your head are all graphs. Even the famous four-colour theorem (any map can be coloured with four colours so that no neighbours match) is a statement about graphs. When Kenneth Appel and Wolfgang Haken proved it in 1976, a computer had to check well over a thousand special cases. Its reliance on a machine started a long argument about whether a proof nobody can read by hand really counts.
Now give every line a number: minutes of driving. The question becomes: what is the quickest route from here to there? With thousands of streets you can't try every route, because the number of routes explodes.
In 1956 a young Dutch programmer, Edsger Dijkstra, was sitting on a café terrace in Amsterdam with his fiancée. By his own later account, he worked out the answer in about twenty minutes, in his head, without pencil or paper. He wanted a demonstration problem for a new computer, the ARMAC. The method was published in 1959 in a paper three pages long.
The idea is a careful kind of greed. Keep a "best time found so far" for every junction. Again and again, pick the unfinished junction with the smallest time; that time is now final, because any other route to it would have to pass through a junction that is already slower. Then see whether going through it improves any of its neighbours. Step through it below.
Numbers on roads are minutes. Tap a road to add traffic (×2), then tap again to close it, and a third time to clear it. Then find the quickest way from Home to Work.
Notice the first surprise: with no traffic, the fastest route goes Home → B → A, a detour, because B is so cheap to reach that the dog-leg (3 minutes) beats the direct road to A (4 minutes). Then jam one road and watch the whole answer reorganise. That is exactly what your phone does when it re-routes you around an accident.
Real road maps have tens of millions of junctions, too many for the plain method to answer instantly. So modern route planners do a lot of work in advance. One widely used technique, contraction hierarchies (published in 2008), precomputes "shortcut" edges so that a search can skip the minor streets and mostly travel along the important roads. But underneath the speed-ups, the logic is the one Dijkstra worked out over a coffee.
Euler solved a puzzle about a real city by refusing to look at the city. That move, keeping only the pattern of connections, turned out to describe friendships, the internet, chemistry and traffic. It is one of the clearest examples of a strange fact about mathematics: the less a description says, the more things it can describe.
A graph keeps only what connects to what. Euler used one to show that the Königsberg walk was impossible: a route crossing every line once needs zero or two dots with an odd number of lines, and Königsberg had four. Give the lines lengths and you can ask for shortest routes. Dijkstra's 1956 method finds them by always finalising the closest unfinished junction next, and its descendants are what route your car today.
Try this: draw your own neighbourhood as a graph, with junctions as dots and streets as lines. Count the odd dots. If there are zero or two, you can walk every street exactly once, and now you know where to start.
Sources. Euler, "Solutio problematis ad geometriam situs pertinentis", Commentarii Academiae Scientiarum Petropolitanae 8 (dated 1736; presented 1735, printed 1741), via MathWorld and the University of Basel. Fate of the bridges: Wikipedia, "Seven Bridges of Königsberg". Milgram's 1967 small-world study and its criticisms; the Erdős number median of 5 (Erdős Number Project, Oakland University). Appel and Haken's 1976 computer-assisted four-colour proof. Dijkstra's café anecdote: his 2001 interview in Communications of the ACM and CWI's history pages; the method appeared in 1959. Contraction hierarchies: Geisberger, Sanders, Schultes and Delling (2008). In node, the interactive's route-finder was checked against a brute-force search of every possible route under all 531,441 combinations of traffic, and the bridge checker against an exhaustive search for every one of the 512 bridge combinations.